import java.util.Arrays;
import java.util.Scanner;

public class Test88 {
    //股票的最大利润包含冷冻期
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n+1][3];
        //0表示买入状态
        //1表示卖出状态
        //2表示冷冻状态
        dp[0][0] = -prices[0];
        for(int i = 1;i<=n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i-1]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]);
            dp[i][2] = dp[i-1][0] + prices[i-1];
        }
        return Math.max(dp[n][1],dp[n][2]);
    }
    //地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 0;i<=m;i++) dp[i][n] = Integer.MAX_VALUE;
        for(int j = 0;j<=n;j++) dp[m][j] = Integer.MAX_VALUE;
        //初识值要正确
        //因为健康点数最小为1
        dp[m][n-1] = dp[m-1][n] = 1;
        for(int i = m-1;i>=0;i--){
            for(int j = n-1;j>=0;j--){
                dp[i][j] = Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j];
                //为什么要与1做比较呢?
                //因为可能为负数 , 健康点数不能为负数
                dp[i][j] = Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
    //使用最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] f = new int[n+1];
        f[n-1] = cost[n-1];
        f[n-2] = cost[n-2];
        for(int i = n-3;i>=0;i--){
            f[i] = Math.min(f[i+1] + cost[i],f[i+2] + cost[i]);
        }
        //下面两种写法都可以
        // return f[0]<f[1]?f[0]:f[1];
        return Math.min(f[0],f[1]);
    }
    //根节点到叶子节点数字之和
//    public int sumNumbers(TreeNode root) {
//        //利用前序遍历进行求解
//        return dfs(root,0);
//    }
//    int dfs(TreeNode root,int sum){
//        sum = root.val+sum*10;
//        if(root.left == null && root.right == null) return sum;
//        int ret = 0;
//        if(root.left != null) ret += dfs(root.left,sum);
//        if(root.right != null) ret += dfs(root.right,sum);
//        return ret;
//    }
    //快速幂
    public double myPow(double x, int n) {
        if(n < 0) return 1.0 / pow(x,-n);
        else return pow(x,n);
    }
    public double pow(double x,int n){
        if(n == 0) return 1.0;
        double temp = pow(x,n/2);
        return n % 2 == 0 ? temp * temp : temp * temp *x;
    }

    //两数相加
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        //虚拟节点方便我们记录结果
//        ListNode newHead = new ListNode(0);
//        //pre方便我们进行连接
//        ListNode pre = newHead;
//        //记录进位
//        int t = 0;
//        while(l1 != null || l2 != null || t != 0){
//            if(l1 != null ) {
//                t+=l1.val;
//                l1 = l1.next;
//            }
//            if(l2 != null){
//                t+=l2.val;
//                l2 = l2.next;
//            }
//            ListNode cur = new ListNode(t % 10);
//            pre.next = cur;
//            pre = pre.next;
//            t/=10;
//        }
//        return newHead.next;
//    }
    public static void main10(String[] args) {
        int[] arr = new int[]{1,1,4,2,3};
        int x = 5;
        int ret = minOperations(arr,x);
        System.out.println(ret);
    }
    public static int minOperations(int[] nums, int x) {
        int ret = -1;
        int sum = 0;
//         int count1 = Integer.MAX.VALUE;
        int count = Integer.MIN_VALUE;
        for(int m:nums) sum+=m;
        if(sum < x) return -1;
        int temp = sum-x;
        int left = 0;
        int right = 0;
        int n = nums.length;
        int sum2 = 0;
        while(right < n){
            sum2+=nums[right];
            while(sum2 > temp){
                sum2-=nums[left++];
            }
            if(sum2 == temp) count = Math.max(count,right-left+1);
            right++;
        }
        return ret == -1 ? 0: n - count;
    }
    public int lengthOfLongestSubstring(String s) {
        //借助哈希表
        int[] map = new int[130];
        int max = 0;
        int left = 0;
        int right = 0;
        int n = s.length();
        while(right < n){
            map[s.charAt(right)]++;
            while(map[s.charAt(right)] >1){
                map[s.charAt(left++)]--;
            }
            max = Math.max(max,right-left+1);
            right++;
        }
        return max;
    }

    public static int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int sum = 0;
        for(int i = 0;i<n;i++){
            int left = i + 1;
            int right = n - 1;
            while(left < right){
                if(nums[i] + nums[left] > nums[right]) {
                    sum+=(right-left);
                    right--;
                }else{
                    left++;
                }

            }
//            i++;
        }
        return sum;

    }
    public static void main3(String[] args) {
//        int[] arr = new int[]{1,0,2,3,0,4,5,0};
        int[] arr = new int[]{0,1,7,6,0,2,0,7};
        duplicateZeros(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void main2(String[] args) {
        int[] arr = new int[]{0,1,0,3,12};
        moveZeroes(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void duplicateZeros(int[] nums) {
        //只利用一个数组,要从后到前进行复写才不会覆盖
        int slow = 0;
        int fast = 0;
        int n = nums.length;
        while(fast < n){
            if(nums[fast] == 0){
                // slow++;
                fast++;
            }
            slow++;
            fast++;
        }
        int cur = slow-1;
        int des = n-1;
        while(cur >= 0){
            if(cur >=0 && (cur == slow && nums[cur] == 0) || nums[cur] != 0) nums[des--] = nums[cur--];
            else if(nums[cur] == 0){
                nums[des--] = 0;
                nums[des--] = 0;
                cur--;
            }
            else nums[des--] = nums[cur--];
        }
    }
    public static void moveZeroes(int[] nums) {
        //待处理区域
        int des = -1;
        int cur = 0;
        int n = nums.length;
        while(cur < n){
            if(nums[cur] != 0){
                des++;
                int temp = nums[des];
                nums[des] = nums[cur];
                nums[cur] = temp;
            }
            cur++;
        }
    }
    public static void main1(String[] args){
        Scanner sc = new Scanner(System.in);
        int fre = sc.nextInt();
        String str = sc.next();
        String[] ss = str.split(",");
        int[] arr = new int[ss.length];
        int j = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 0;i<ss.length;i++){
            String temp = ss[i].substring(0,4);
            int temp2 = Integer.valueOf(temp);
            if(fre > temp2){
                arr[j] = fre - temp2;
            }else{
                arr[j] = temp2 - fre;
            }
            if(min > arr[j]) min = arr[j++];
        }

        //定义标记数组
        // boolean[] isMin = new boolean[arr.length];
        double ret = 0.0;
        for(int i =0;i < arr.length-1;i++){
            if(arr[i] == min && arr[i+1] == min){
                ret = ((double)Integer.valueOf(ss[i].substring(5,7)) + (double)Integer.valueOf(ss[i+1].substring(5,7)))/2.0;
            }else{
                ret = (double)Integer.valueOf(ss[i].substring(5,7)) ;
            }
        }
        System.out.print(ret);
    }
}
